#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval)
    {
        vector<vector<int>> result;
        int L = newInterval[0], R = newInterval[1];
        int flag = 0;
        for (int i = 0; i < intervals.size(); ++i)
        {
            if (intervals[i][0] > R)//不用合并,直接插入intervals[i]的前面
            {
                if (flag == 0)
                {
                    result.push_back({ L,R });
                    flag = 1;
                }
                result.push_back(intervals[i]);
            }
            else if (intervals[i][1] < L)//不用合并,可能插入到intervals的后面,或者合并
            {
                result.push_back(intervals[i]);
            }
            else//需要合并
            {
                L = min(L, intervals[i][0]);//更新L和R
                R = max(R, intervals[i][1]);
            }
        }
        if (flag == 0)
        {
            result.push_back({ L,R });
        }
        return result;
    }
};

/*
给你一个 无重叠的 ，按照区间起始端点排序的区间列表。
在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。

示例 1：
输入：intervals = [[1,3],[6,9]], newInterval = [2,5]
输出：[[1,5],[6,9]]
*/

